public class 同时运行N台电脑的最长时间 {

    //https://leetcode.cn/problems/maximum-running-time-of-n-computers/description/

    //方法一(没有经过优化的版本)
    public long maxRunTime(int n, int[] batteries) {
        //确认二分范围[0,sum / n]
        long sum = 0;
        for(int i = 0;i < batteries.length;i++){
            sum += batteries[i];
        }
        long l = 0;
        long r = sum;
        long ret = 0;
        while(l <= r){
            long m = (l + r) / 2;
            //让每台电脑运行m分钟可以做到几台
            //如果大于等于就往左边找找有没有更大一点的
            if(f(batteries,m) >= n){
                l = m + 1;
                ret = m;
            }else{
                r = m - 1;
            }
        }
        return ret;
    }

    public long maxRunTime1(int n, int[] batteries) {
        //确认二分范围[0,sum / n]
        long sum = 0;
        int max = 0;
        //找到最大值
        for(int i = 0;i < batteries.length;i++){
            sum += batteries[i];
            max = Math.max(max,batteries[i]);
        }
        //sum和大于最大电池量和几台电脑的值
        //也就是碎片电池可以拼接而成, 直接返回即可
        if(sum > n * (long)max){
            return sum / n;
        }
        //并且缩小了遍历的范围
        long l = 0;
        long r = max;
        long ret = 0;
        while(l <= r){
            long m = (l + r) / 2;
            //让每台电脑运行m分钟可以做到几台
            if(f(batteries,m) >= n){
                l = m + 1;
                ret = m;
            }else{
                r = m - 1;
            }
        }
        return ret;
    }

    public long f(int[] nums,long mid){
        long part = 0;
        long sum = 0;
        if(mid == 0){
            return Integer.MAX_VALUE;
        }
        //一个电池如果大于那台电脑所用的时间, 这个电池专门为他供电
        for(int num : nums){
            if(num >= mid){
                part++;
            }else{
                sum += num;
            }
        }
        part += sum / mid;
        return part;
    }
}
